package Q563;

/**
 * 二叉树的坡度
 * 一个树的 节点的坡度 定义即为，该节点左子树的节点之和和右子树节点之和的 差的绝对值 。如果没有左子树的话，左子树的节点之和为 0 ；没有右子树的话也是一样。空结点的坡度是 0 。
 * <p>
 * 整个树 的坡度就是其所有节点的坡度之和。
 *
 * @author 23737
 * @time 2021.11.18
 */
public class Test {
    public static void main(String[] args) {
        TreeNode treeNode = new TreeNode(4);
        TreeNode treeNode2 = new TreeNode(2);
        TreeNode treeNode3 = new TreeNode(9);
        TreeNode treeNode4 = new TreeNode(3);
        TreeNode treeNode5 = new TreeNode(5);
        TreeNode treeNode6 = new TreeNode(7);
        treeNode.left = treeNode2;
        treeNode.right = treeNode3;
        treeNode2.left = treeNode4;
        treeNode2.right = treeNode5;
        treeNode3.left = null;
        treeNode3.right = treeNode6;
        System.out.println(new Solution().findTilt(treeNode));
        System.out.println(new Solution2().findTilt(treeNode));
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    TreeNode() {
    }

    TreeNode(int val) {
        this.val = val;
    }

    TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }
}

class Solution {
    public int findTilt(TreeNode root) {
        if (root == null){
            return 0;
        }
        return dfs(root);
    }

    public int dfs(TreeNode treeNode) {
        int count = 0;
        if (treeNode.left == null && treeNode.right == null) {
            return treeNode.val;
        }else if (treeNode.left != null && treeNode.right != null) {
            count += Math.abs(dfs(treeNode.left) - dfs(treeNode.right));
        }else {
            count += treeNode.left == null? Math.abs(treeNode.right.val):Math.abs(treeNode.left.val);
        }
        return count;
    }
}

class Solution2 {

    private int result;

    public int findTilt(TreeNode root) {
        this.result = 0;
        dfs(root);
        return this.result;
    }

    private int dfs(TreeNode root) {
        if (root == null) {
            return 0;
        }
        int left = dfs(root.left);
        int right = dfs(root.right);
        this.result += Math.abs(left - right);
        return left + right + root.val;
    }

}
